package io.github.consoles.dsa;

/**
 * Created by yiihua-013 on 17/6/11.
 * <p>
 * 前移编码
 * <p>
 * 从stdio中读取字符串,使用链表保存这些字符并清除重复字符。
 * 当读取了一个从未见过的字符时,将其插入表头
 * 当读取了一个重复的字符时将其从表中删除并再次插入表头。
 * <p>
 * 前移编码策略假设最近访问过的元素很可能会被再次访问(LRU)、因此可以用于缓存、数据压缩等许多场景
 */
public class MoveToFront {

    private LinkedList<Character> list = new LinkedList<>();

    public MoveToFront(String str) {
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (list.find(c)) {
                list.remove(c);
            }
            list.insertBeforeFirst(list.createNode(c));
        }
    }

    String getCode() {
        String str = "";
        for (char c : list) {
            str += c;
        }
        return str;
    }
}
